//快排
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
    void qsort(vector<int>& nums,int l,int r)
    {
        if(l>=r) return;
        int tmp=getrand(nums,l,r);
        int left=l-1,right=r+1;
        int i=l;
        while(i<right)
        {
            if(nums[i]<tmp)
            {
                left++;
                swap(nums[i],nums[left]);
                i++;
            }
            else if(nums[i]==tmp)
            {
                i++;
            }
            else
            {
                right--;
                swap(nums[i],nums[right]);
            }
        }
        //[l,left][left+1,right-1][right,r]
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    int getrand(vector<int>nums,int l,int r)
    {
        int x=rand();
        return nums[x%(r-l+1)+l];
    }
};

//颜色分类
class Solution {
public:
    void sortColors(vector<int>& nums) 
    {
        //分成三个区域
        //可以用两个指针进行辅助
        //l是0的最右边的下标
        //r是2的最左边下标
        int l=-1,r=nums.size();
        int i=0;
        while(i<r)
        {
            if(nums[i]==0)
            {
                l++;
                swap(nums[i],nums[l]);
                i++;
            }
            else if(nums[i]==1)
            {
                i++;
            }
            else
            {
                r--;
                swap(nums[i],nums[r]);
            }
        }
    }
};


